package ljl.alg.wangzheng_camp.round1.bitwise;

/**
 * 我一上来有点蒙了
 * */
public class _17_04_missing_number {
    
    /**
     * 两个办法
     * 1. 求和公式算出来 0..n 总和，再做差找
     * 2. 利用位运算，nums 全异或，再异或 0..n 最后得结果
     * */
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        for (int i = 0; i <= nums.length; i++) {
            res ^= i;
        }
        return res;
    }
    
    public int missingNumber2(int[] nums) {
        int n = nums.length;
        int total = n * (n + 1) / 2;
        for (int num : nums) {
            total -= num;
        }
        return total;
    }
}
